#ifndef TACORES_GRAPH_H
#define TACORES_GRAPH_H

using namespace std;

#include <list>
#include <vector>
#include <functional>
#include <algorithm>

enum vertexColor { White, Gray, Black };
enum edgeType { Tree, Backward, Forward, Cross };

// For vertex u, stores information about (v,w)
typedef pair<int,int> IntegerPair;
typedef list<IntegerPair> VertexList;

struct IntegerPairCompare : public binary_function<IntegerPair, int, bool>
{
	bool operator() (const IntegerPair p, int v) const
	{
		if(p.first == v)
		{
			return true;
		}
		return false;
	}
};

class Graph
{
public:
	Graph(int n, bool directed)
	{
		n_ = n;
		directed_ = directed;
		vertices_.resize(n);
	}
	~Graph() {}

	bool directed() const { return directed_; }
	int numVertices() const { return n_; }

	bool isEdge(int u, int v) const
	{
		int dummy = 0;
		return isEdge(u, v, dummy);
	}

	bool isEdge(int u, int v, int& weight) const
	{
		VertexList::const_iterator end = vertices_[u].end();
		VertexList::const_iterator it = find_if( vertices_[u].begin(), end,
				bind2nd<IntegerPairCompare>(IntegerPairCompare(), v));
		if(it != end)
		{
			weight = it->second;
			return true;
		}
		return false;
	}

	int edgeWeight(int u, int v) const
	{
		int weight = 0;
		isEdge(u, v, weight);
		return weight;
	}

	void addEdge(int u, int v)
	{
		addEdge(u, v, 0);
	}

	void addEdge(int u, int v, int weight)
	{
		if(isEdge(u,v)) return;
		IntegerPair p(v, weight);
		vertices_[u].push_back(p);
		if(!directed_)
		{
			IntegerPair p(u, weight);
			vertices_[v].push_back(p);
		}
	}

	void removeEdge(int u, int v)
	{
		vertices_[u].remove_if(
				bind2nd<IntegerPairCompare>(IntegerPairCompare(), v));
		if(!directed_)
		{
			vertices_[v].remove_if(
					bind2nd<IntegerPairCompare>(IntegerPairCompare(), u));
		}
	}

	VertexList::const_iterator begin(int u) const
	{
		return vertices_[u].begin();
	}

	VertexList::const_iterator end(int u) const
	{
		return vertices_[u].end();
	}

private:
	vector<VertexList> vertices_;
	int n_;
	bool directed_;

	Graph(const Graph&);
};
typedef Graph G;

#endif

